# 33/100 链表-排序链表
# leetcode第148题: https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/3
from typing import Optional

import numpy.random

from leetcode.bds import ListNode, ListConvert
from leetcode.test import test_function as tf
import numpy as np


def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
    """使用内置排序算法, 缺点是维护了一个长度为n的list)"""
    curr = head
    head = ListNode(0, head)
    sl = []
    while curr:
        sl.append(curr)
        curr = curr.next
    sl = sorted(sl, key=lambda node: - node.val)
    curr = head
    while sl:
        curr.next = sl.pop()
        curr = curr.next
    curr.next = None
    return ListConvert.link_to_list(head.next)


def sortList_opt(head: Optional[ListNode]) -> Optional[ListNode]:
    """使用归并排序
    归并排序分为 自顶向下 和 自下而上 两种, 这里采用的是自下而上的, 优点是常数级的空间复杂度
    自顶向下的排序现将元素逐个分为两两一组进行大小比较并排序, 然后逐组合并
    自下向上的排序将整个集合分为两组, 然后每组再分, 直到每组为两个, 排序后合并, 然后逐步排序再合并
    """

    def merge(head1: ListNode, head2: ListNode) -> ListNode:
        """排序合并两个组的函数, 和 'g_link6_lc121.py' 合并有序数组中的方法一样
        see: https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
        """
        dummy_head = ListNode(0)
        temp, temp1, temp2 = dummy_head, head1, head2
        while temp1 and temp2:
            if temp1.val <= temp2.val:
                temp.next = temp1
                temp1 = temp1.next
            else:
                temp.next = temp2
                temp2 = temp2.next
            temp = temp.next
        temp.next = temp1 if temp1 else temp2
        return dummy_head.next

    if not head:
        return ListConvert.link_to_list(head)

    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    dummy_head = ListNode(0, head)
    sub_length = 1
    while sub_length < length:
        prev, curr = dummy_head, dummy_head.next
        while curr:
            head1 = curr
            for i in range(1, sub_length):
                if curr.next:
                    curr = curr.next
                else:
                    break
            head2 = curr.next
            curr.next = None
            curr = head2
            for i in range(1, sub_length):
                if curr and curr.next:
                    curr = curr.next
                else:
                    break

            succ = None  # 用于存储下一组子链表的起始节点
            if curr:
                succ = curr.next
                curr.next = None

            merged = merge(head1, head2)
            prev.next = merged
            while prev.next:
                prev = prev.next
            curr = succ
        sub_length <<= 1  # 相当于subLenth *= 2

    return ListConvert.link_to_list(dummy_head.next)


if __name__ == '__main__':
    head1 = ListConvert.list_to_link([4, 2, 1, 3])
    head2 = ListConvert.list_to_link([-1, 5, 3, 4, 0])
    head3 = ListConvert.list_to_link([])
    # 使用numpy生成一个长数组
    numpy.random.seed(42)
    np_list = list(np.random.randint(low=0, high=1000, size=200))
    res_np = sorted(np_list)
    head4 = ListConvert.list_to_link(np_list)

    inp = [{"head": head1}, {"head": head2}, {"head": head3}, {"head": head4}, ]
    out = [[1, 2, 3, 4], [-1, 0, 3, 4, 5], [], res_np]

    tf(sortList, inp, out)
    tf(sortList_opt, inp, out)
